import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Solution864 {
    public int shortestPathAllKeys(String[] grid) {
        Map<Character, int[]> map=new HashMap<>();
        Map<Character,Integer> map1=new HashMap<>();
        int sx=0,sy=0,cur=0;
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length();j++){
                if (grid[i].charAt(j)=='@'){
                    sx=i;
                    sy=j;
                }else if (grid[i].charAt(j)>='a' && grid[i].charAt(j)<='f'){
                    map.put(grid[i].charAt(j), new int[]{i,j});
                    map1.put((char)(grid[i].charAt(j)-32),cur);
                    cur++;
                }
            }
        }
        int[][] f=new int[1<<map.size()][map.size()];
        for (int i=0;i<f.length;i++){
            Arrays.fill(f[i],Integer.MAX_VALUE);
        }
        f[0][0]=0;
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{0,sx,sy,0});
        while (!queue.isEmpty()){
            int[] p=queue.poll();
            int state=p[0];
            for (Map.Entry<Character, int[]> entry : map.entrySet()) {
                int v=map1.get((char)(entry.getKey()-32));
                if ((state&(1<<v))==0){
                    int dis=find(grid,new int[]{p[1],p[2],entry.getValue()[0],entry.getValue()[1]},state,map1);
                    if (dis!=-1 && f[state|(1<<v)][v]>f[state][p[3]]+dis){
                        f[state|(1<<v)][v]=f[state][p[3]]+dis;
                        queue.offer(new int[]{state|(1<<v),entry.getValue()[0],entry.getValue()[1],v});
                    }
                }
            }
        }
        int ans=Integer.MAX_VALUE;
        for (int i=0;i<map.size();i++){
            if (f[(1<<map.size())-1][i]<ans){
                ans=f[(1<<map.size())-1][i];
            }
        }
        return ans==Integer.MAX_VALUE?-1:ans;
    }

    private int find(String[] grid, int[] ints, int state, Map<Character, Integer> map) {
        int[] dx=new int[]{1,0,-1,0};
        int[] dy=new int[]{0,1,0,-1};
        int[][] visit=new int[grid.length][grid[0].length()];
        for (int i=0;i<grid.length;i++){
            Arrays.fill(visit[i],-1);
        }
        visit[ints[0]][ints[1]]=0;
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{ints[0],ints[1]});
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            if (t[0]==ints[2] && t[1]==ints[3]){
                return visit[t[0]][t[1]];
            }
            for (int i=0;i<4;i++){
                int x=t[0]+dx[i];
                int y=t[1]+dy[i];
                if (x>=0 && x<grid.length && y>=0 && y<grid[0].length() && grid[x].charAt(y)!='#'){
                    boolean flag=true;
                    if (grid[x].charAt(y)>='A' && grid[x].charAt(y)<='F'){
                        if ((state&(1<<map.get(grid[x].charAt(y))))==0){
                            flag=false;
                        }
                    }
                    if (flag && visit[x][y]==-1){
                        visit[x][y]=visit[t[0]][t[1]]+1;
                        queue.offer(new int[]{x,y});
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution864().shortestPathAllKeys(new String[]{"Dd#b@",".fE.e","##.B.","#.cA.","aF.#C"}));
    }
}
